package github.lyf.middle;


import com.sun.xml.internal.ws.api.pipe.ServerTubeAssemblerContext;
import org.omg.CORBA.PUBLIC_MEMBER;

/**
 * @author yunfei.li
 * @date 2021/9/28 17:35
 */
public class PathSum {
    /**
     * 给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
     * <p>
     * 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）
     * 二叉树的节点个数的范围是 [0,1000]
     * -109 <= Node.val <= 109
     * -1000 <= targetSum <= 1000
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/path-sum-iii
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param root
     * @param targetSum
     * @return
     */
    public static int count;

    public static int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        int currNum = 0;
        dfs(root, currNum, targetSum);
        pathSum(root.right, targetSum);
        pathSum(root.left, targetSum);
        return count;
    }

    public static void dfs(TreeNode child, int currNum, int targetSum) {
        if (child == null) {
            return;
        }
        currNum = currNum + child.val;
        if (currNum == targetSum) {
            count++;

        }
        dfs(child.left, currNum, targetSum);
        dfs(child.right, currNum, targetSum);
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

}
